package leetcode.code139;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 学来的
 * @author CaoYu
 * @date 2021年9月14日
 * @description
 */
public class Solution2 extends Solution139 {

	@Override
	public boolean wordBreak(String s, List<String> wordDict) {
		Set<String> wordDictSet = new HashSet<>(wordDict);
		boolean[] dp = new boolean[s.length() + 1];
		dp[0] = true;
		for (int i = 1; i <= s.length(); i++) {
			for (int j = 0; j < i; j++) {
				if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
					dp[i] = true;
					break;
				}
			}
		}
		return dp[s.length()];
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1("leetsscode");
		so.debug2();
		so.debug3();
		so.debug4();
//		System.out.println((int) 'a');
//		System.out.println((int) 'z');
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

}
